1. Field of the Invention
The present invention relates to image segmentation, and more particularly to methods and systems for image segmentation using isoperimetric trees.
2. Description of the Related Art
Medical imaging is generally recognized as important for diagnosis and patient care with the goal of improving treatment outcomes. In recent years, medical imaging has experienced an explosive growth due to advances in imaging modalities such as x-rays, computed tomography (CT), magnetic resonance imaging (MRI) and ultrasound. These modalities provide noninvasive methods to study internal organs in vivo, but the amount of data is high and when presented as 2D images generally require an anatomist/radiology specialist for interpretation. Unfortunately, the cost incurred in manual interpretation of this data is prohibitive for routine data analysis.
The 2-D slices can be combined to generate a 3-D volumetric model. When the images are taken over time, 4-D (3-D+time) analysis is possible. The accurate and expedient interpretation of this data is difficult to achieve.
Image segmentation plays an important role in computer-based medical applications for diagnosis and analysis of anatomical data by enabling automatic or semi-automatic extraction of an anatomical organ or region of interest from a dataset. For example, image segmentation methods enable the separation of the brain from non-brain tissue, also known as skull-stripping, which is an important and difficult image processing problem in brain mapping research. Image segmentation methods enable the study of the shape and motion of the heart. The study of the mechanics of the heart is important because heart diseases are thought to be strongly correlated to regional changes in the heart's shape and motion.
Methods of graph partitioning in image segmentation that have gained prominence in the computer vision literature include the normalized cuts algorithm, max-flow/min-cut, and the random walker algorithm. Shi, J. and Malik, J., “Normalized cuts and image segmentation,” In IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8): 888-905, 2000. Boykov, Y. and Jolly, M.-P., “Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images,” In International Conference on Computer Vision, volume 1, pages 105-112, July 2001. Yu constructs a multiple level graph encoding cues at different image scales, and optimizes the average Ncut cost across all graph levels. Yu, Stella X., “Segmentation Using Multiscale Cues,” In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1(1): 247-254, 2004.
Grady introduced the isoperimetric graph partitioning algorithm as a method of fully-automatic image segmentation. Grady, Leo, “Space-variant computer vision: A graph-theoretic approach,” Ph.D. dissertation, Boston University, Boston, Mass., 2004. However, because the algorithm allows specification of a single node as the foreground point around which the segmentation is based, this point may be chosen by a user, yielding a semi-automatic segmentation algorithm. The isoperimetric algorithm is formulated on a graph where, in the image processing context, each node represents a voxel and edges connect neighboring voxels in a 6-connected lattice.